package src.dp.entire_bag;

import java.util.Scanner;

public class kama52 {//完全背包

    /**
     * 1. dp数组下标含义：一维dp数组，容量 j 的背包，价值总和最大是 dp[j]
     * 2. 递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
     * 3. 初始化数组：一维不用初始化
     * 4. 遍历顺序：对于纯粹的完全背包问题，遍历物品和背包的顺序可以交换。遍历背包时 从小到大
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  //物品种类
        int bagWeight = sc.nextInt();  //背包容量
        int[] weight = new int[n];
        int[] value = new int[n];

        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }

        int[] dp = new int[bagWeight + 1];
        //初始化第一行
//        for (int j = weight[0]; j < bagWeight; j++) {
//            dp[0][j] = value[0];
//        }

        //先物品后背包
        for (int i = 0; i < n; i++) {
            for (int j = weight[i]; j <= bagWeight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //先背包后物品
        for (int j = 0; j <= bagWeight; j++) {
            for (int i = 0; i < n; i++) {
                if (j >= weight[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }

        System.out.println(dp[bagWeight]);

    }
}
